# -- coding: gbk --
import mip
from mip import Model, BINARY, xsum, minimize
# from enum import Enum
import networkx as nx
from matplotlib import pyplot as plt


# 路网
class Network:
    def __init__(self):
        self.NodeList = []
        self.EdgeList = []
        self.ODList = []
        self.PrevEdge = {}  # 节点入弧
        self.NextEdge = {}  # 节点出弧

    def add_node(self, node):
        self.NodeList.append(node)
        self.PrevEdge[node] = []
        self.NextEdge[node] = []

    # 通过车站名称获取区间
    def get_edge(self, sta1, sta2):
        for sec in self.EdgeList:
            if sec.start_station == sta1 and sec.end_station == sta2:
                return sec

    # 增加区间
    def add_edge(self, s_node, e_node, distance):
        if s_node not in self.NodeList:
            self.add_node(s_node)
        if e_node not in self.NodeList:
            self.add_node(e_node)
        for edge in self.EdgeList:
            if s_node == edge.start_station and e_node == edge.end_station:
                return
        edge = Edge(s_node, e_node, distance)
        self.EdgeList.append(edge)
        if e_node not in self.PrevEdge.keys():
            self.PrevEdge[e_node] = [edge]
        else:
            self.PrevEdge[e_node].append(edge)
        if s_node not in self.NextEdge.keys():
            self.NextEdge[s_node] = [edge]
        else:
            self.NextEdge[s_node].append(edge)

# 弧段
class Edge:
    def __init__(self, start_node, end_node, distance):
        self.start_station = start_node
        self.end_station = end_node
        self.distance = distance


class Section:
    def __init__(self, start_node, end_node, capacity):
        self.start_station = start_node
        self.end_station = end_node
        self.capacity = capacity


# 各产品的运输需求
class ODFlow:
    def __init__(self):
        self.Id = 0  # 编号
        self.Origin = ''  # 出发地
        self.Destination = ''  # 目的地
        self.Num = 0  # 重量
        self.shortest_distance = 0


class Demand:
    def __init__(self):
        self.Flows = []

    def add_flow(self, origin, dest, num):
        flow = ODFlow()
        flow.Origin = origin
        flow.Destination = dest
        flow.Num = num
        self.Flows.append(flow)

    def get_flow_num(self, origin, dest):
        result = list(filter(lambda x: x.Origin == origin and x.Destination == dest, self.Flows))
        if len(result) > 0:
            return result[0].Num
        else:
            return 0

    def get_flow(self, origin, dest):
        result = list(filter(lambda x: x.Origin == origin and x.Destination == dest, self.Flows))
        if len(result) > 0:
            return result[0]
        else:
            return None


# 路径
class Route:
    def __init__(self, *list):
        self.List = list

def glb_generate_test_world():
    section_list = []
    section_list.append(Section("1", "2",300))
    section_list.append(Section("1", "4", 300))
    section_list.append(Section("1", "2", 210))
    section_list.append(Section("1", "4", 300))
    section_list.append(Section("2", "3", 300))
    section_list.append(Section("2", "6", 300))
    section_list.append(Section("3", "9", 380))
    section_list.append(Section("4", "5", 300))
    section_list.append(Section("4", "7", 300))
    section_list.append(Section("5", "6", 300))
    section_list.append(Section("5", "8", 380))
    section_list.append(Section("6", "9", 380))
    section_list.append(Section("6", "10", 300))
    section_list.append(Section("6", "11", 300))
    section_list.append(Section("9", "12", 300))
    section_list.append(Section("10", "11", 300))
    section_list.append(Section("10", "13", 300))
    section_list.append(Section("11", "12", 300))
    section_list.append(Section("11", "14", 300))
    section_list.append(Section("13", "14", 300))
    section_list.append(Section("7", "8", 380))
    section_list.append(Section("8", "10", 400))

    net = Network()
    net.add_edge("1", "2", 210)
    net.add_edge("1", "4", 265)
    net.add_edge("2", "3", 232)
    net.add_edge("2", "6", 123)
    net.add_edge("3", "9", 480)
    net.add_edge("4", "5", 109)
    net.add_edge("4", "7", 190)
    net.add_edge("5", "6", 172)
    net.add_edge("5", "8", 149)
    net.add_edge("6", "9", 368)
    net.add_edge("6", "10", 246)
    net.add_edge("6", "11", 280)
    net.add_edge("9", "12", 503)
    net.add_edge("10", "11", 130)
    net.add_edge("10", "13", 115)
    net.add_edge("11", "12", 336)
    net.add_edge("11", "14", 218)
    net.add_edge("13", "14", 158)
    net.add_edge("7", "8", 117)
    net.add_edge("8", "10", 220)

    net.add_edge("2", "1", 210)
    net.add_edge("4", "1", 265)
    net.add_edge("3", "2", 232)
    net.add_edge("6", "2", 123)
    net.add_edge("9", "3", 480)
    net.add_edge("5", "4", 109)
    net.add_edge("7", "4", 190)
    net.add_edge("6", "5", 172)
    net.add_edge("8", "5", 149)
    net.add_edge("9", "6", 368)
    net.add_edge("10", "6", 246)
    net.add_edge("11", "6", 280)
    net.add_edge("12", "9", 503)
    net.add_edge("11", "10", 130)
    net.add_edge("13", "10", 115)
    net.add_edge("12", "11", 336)
    net.add_edge("14", "11", 218)
    net.add_edge("14", "13", 158)
    net.add_edge("8", "7", 117)
    net.add_edge("10", "8", 220)

    demand = Demand()
    demand.add_flow("3", "7", 55)
    demand.add_flow("7", "9", 35)
    demand.add_flow("7", "14", 50)
    demand.add_flow("12", "7", 45)
    demand.add_flow("8", "9", 64)
    demand.add_flow("8", "12", 52)
    demand.add_flow("1", "8", 60)
    demand.add_flow("1", "14", 40)
    demand.add_flow("12", "1", 50)
    demand.add_flow("3", "8", 65)
    demand.add_flow("3", "11", 52)
    demand.add_flow("10", "3", 40)
    demand.add_flow("2", "12", 50)
    demand.add_flow("4", "9", 45)
    demand.add_flow("11", "4", 46)
    demand.add_flow("5", "13", 70)
    demand.add_flow("5", "12", 68)
    demand.add_flow("14", "5", 62)
    demand.add_flow("3", "13", 50)
    demand.add_flow("10", "1", 45)
    return net, demand, section_list


def glb_finding_path(net, demand):  # 定义了一个函数glb_finding_path,作用是寻找从一个起点到终点的路径.
    # 创建图
    G = nx.DiGraph()  # 创建了一个空的有向图G
    for edge in net.EdgeList:  # for循环，用于遍历problem_input对象的EdgeList属性中的每个边
        G.add_edge(edge.start_station, edge.end_station, weight=edge.distance)
    for i in net.NodeList:
        for j in net.NodeList:
                flow = demand.get_flow(i, j)
                if flow is not None:
                    flow.shortest_distance = nx.dijkstra_path_length(G, i, j, "distance")
    # 在循环体内，向有向图G中添加一个边。这个边连接edge.start_station和edge.end_station，并将权重设置为edge.Distance
    # 绘制路网图
    nx.draw(G, with_labels=True)  # 使用NetworkX的draw函数绘制有向图G。参数with_labels=True表示将显示节点的标签
    plt.title('Continue in 5 seconds')
    plt.axis('on')
    plt.xticks([])
    plt.yticks([])
    plt.savefig('路网图.png')
    # plt.show()  # 显示图表


def glb_solve_mip(net, demand, section_list):
    model = Model()
    y = {(i, j, e): model.add_var(var_type=BINARY) for i in net.NodeList for j in net.NodeList for e in net.EdgeList}
    model.objective = minimize(xsum(y[i, j, e] * e.distance * demand.get_flow_num(i, j) for i in net.NodeList for j in net.NodeList for e in net.EdgeList))

    for i in net.NodeList:
        for j in net.NodeList:
            if demand.get_flow_num(i, j) > 0:
                model += xsum(y[i, out_edge.end_station, out_edge] for out_edge in net.NextEdge[i]) == 1

    for i in net.NodeList:
        for j in net.NodeList:
            if i == j:
                continue
            for node in net.NodeList:
                if i == node:
                    model += xsum(y[i, j, out_edge] for out_edge in net.NextEdge[node]) - xsum(y[i, j, in_edge] for in_edge in net.PrevEdge[node]) == 1
                elif j == node:
                    model += xsum(y[i, j, out_edge] for out_edge in net.NextEdge[node]) - xsum(y[i, j, in_edge] for in_edge in net.PrevEdge[node]) == -1
                else:
                    model += xsum(y[i, j, out_edge] for out_edge in net.NextEdge[node]) - xsum(y[i, j, in_edge] for in_edge in net.PrevEdge[node]) == 0

    for sec in section_list:
        edge1 = net.get_edge(sec.start_station, sec.end_station)
        edge2 = net.get_edge(sec.end_station, sec.start_station)
        model += xsum((y[i, j, edge1] + y[i, j, edge2]) * demand.get_flow_num(i, j) for i in net.NodeList for j in net.NodeList) <= sec.capacity

    for i in net.NodeList:
        for j in net.NodeList:
            flow = demand.get_flow(i, j)
            if flow is not None:
                model += xsum(y[i, j, edge] for edge in net.EdgeList) <= 1.2 * flow.shortest_distance  # 最大绕行率取2

    # 求解
    # model.write("model.lp")
    model.max_mip_gap = 0.01
    model.verbose = 1
    model.optimize(max_seconds=300)

    # 输出
    if model.num_solutions:
        print('目标函数值:', format(model.objective_value))
        print("{:<8} {:<10} {:<55}".format("发站", "到站", "路径"))
        for i in net.NodeList:
            for j in net.NodeList:
                if demand.get_flow_num(i, j) == 0:
                    continue
                cur_node = i
                route = []
                while cur_node != j:
                    for edge in net.EdgeList:
                        if y[i, j, edge].x == 1 and edge.start_station == cur_node:
                            if cur_node != j:
                                route.append(edge.end_station)
                            cur_node = edge.end_station
                print("{:<8} {:<10} {:<55}".format(i, j, '{0}->{1}'.format(i, '->'.join(route))))


# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    net, demand, section_list= glb_generate_test_world()
    glb_finding_path(net, demand)
    glb_solve_mip(net, demand, section_list)